1283D - Christmas Trees - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
///  order_of_key return number of elements less than x.
///  find_by_order return index.

const int N =  3*1e5 + 10;
const int M = 998244353;

#define ll long long int
#define ld long double
#define rep(i, n) for (ll i = 0; i < n; i++)
#define ff first
#define ss second
#define rep1(i, n) for (ll i = 1; i < n; i++)
#define repr(i, n) for (ll i = n - 1; i >= 0; i--)
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define vpll vector<pair<ll, ll>>
#define vvll vector<vector<ll>>
#define vvpll vector<vector<pll>>
#define pll pair<ll, ll>
const ll INF = LLONG_MAX;
ll binmult(int a, int b)
{
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1)
            ans = (ans + a) % M;
        a = (a + a) % M;
        b >>= 1;
    }
    return ans;
}
ll binpow(int a, int b)
{
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = binmult(ans, a);
        a = binmult(a, a);
        b >>= 1;
    }
    return ans;
}
ll bs_sqrt(ll x)
{
    ll left = 0, right = 2000000123;
    while (right > left)
    {
        ll mid = (left + right) / 2;
        if (mid * mid > x)
            right = mid;
        else
            left = mid + 1;
    }
    return left - 1;
}
ll inverse(ll x,ll M){
    ll y=binmult(x,M-2);
    return y;
}

// ll nCr(ll n, ll r)
// {
//     return ((fac(n)*inverse(fac(n-r)))%M*inverse(fac(r)))%M;
// }

//----------------------------------------------------------------------
// DSU
// vll par(N+1,0),sz(N+1,0);
// void make(int x){
//     par[x]=x;sz[x]=1;
// }
// int find(int x){
//     if(x==par[x]) return x;
//     return par[x]=find(par[x]);
// }
// void Union(int b,int a){
//     a=find(a),b=find(b);
//     // if(a!=b)
//     {
        
//         if(sz[a]<sz[b]) swap(a,b);
//         sz[a]+=sz[b];
//         par[b]=a;
//     }
// }
//--------------------------------------------------------------------
// Dynamic Range Minimum Segment Tree

// vll a(N), seg(4*N);
// void build(int ind, int low, int high){
//     if(low==high) {seg[ind]=a[low]; return ;}
//     ll mid=(high+low)/2;
//     build(2*ind+1, low, mid);
//     build(2*ind+2, mid+1,high);
//     seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
// }
// void update(ll ind, ll low,ll high, ll i, ll val){
//     if(low==high ){
//         if(low==i)
//         seg[ind]=val;
//         return ;
//     }
//     if(i<low || i>high) return ;
//     ll mid=(high+low)/2;
//     update(2*ind+1,low, mid, i, val);
//     update(2*ind+2,mid+1, high, i, val);
//     seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
//     return ;
// }
// ll query(ll ind, ll low,ll high, ll l, ll r){
//     if(l<=low && high<=r) return seg[ind];
//     if(high< l || low>r) return INT_MAX;
//     ll mid=(high+low)/2;
//     return min(query(2*ind+1, low, mid, l, r), query(2*ind+2, mid+1, high, l, r));
// }
//-----------------------------------------------------------------------
bool comp(pll &p, pll &q){
    if(p.ff== q.ff) return p.ss>q.ss;
    return p.ff<q.ff;
}
bool comp2(pll &p, pll &q){
    if(p.ff== q.ff) return p.ss>q.ss;
    return p.ff<q.ff;
}


// // vll dis(N,-INF), dis2()
// vpll dis(N), dis2(N);
// void dfs(ll i, vll &vis, vvll &g, vll &a){
//     vis[i]=1;
//     ll mx=0, mx2=0;
//     for(auto it: g[i]){
//         if(vis[i]) continue;
//         dfs(it,vis,g,a);
//         if(mx <= dis[it].ff) mx2=mx, ind2=ind1, ind1=it, mx=dis[it].ff;
//         else if(mx2 <= dis[it].ff ){

//         }
//     }
// }

void solve()
{
    ll n,m;cin>>n>>m;
    vll a(n);
    rep(i,n) cin>>a[i];
    sort(a.begin(), a.end());

    vll b=a;
    rep(i,n) b[i]*=-1;
    sort(b.begin(), b.end());
    
    queue<ll> q;
    map<ll,ll> mp;
    ll c=0;
    rep(i,n){
        q.push(a[i]);
        mp[a[i]]++;
    }
    // map<ll,ll> mp;
    vll v;
    while(!q.empty()){
        auto cur=q.front();
        q.pop();
        if(mp.find(cur-1)==mp.end()) {q.push(cur-1);mp[cur-1]++; v.pb(cur-1);}
        if(mp.find(cur+1)==mp.end()) {q.push(cur+1);mp[cur+1]++; v.pb(cur+1);}
        if(v.size()>=m) break;
    }
    // cout<<v.size()<<endl;
    ll d=0;
    rep(i,m){
        ll l=lower_bound(a.begin(), a.end(), v[i])-a.begin();
        ll u=lower_bound(b.begin(), b.end(), -v[i])-b.begin();

        ll mn=M;
        if(l!=a.size()) mn=abs(v[i]-a[l]);
        if(u!=b.size()) mn=min(mn,abs(v[i]+b[u]));
        // if(mn==M) cout<<i<<" "<<v[i]<<"\n";
        d+=mn;
    }
    cout<<d<<endl;
    rep(i,m) cout<<v[i]<<" ";
    cout<<endl;
}
    
//a[i]>=ur[i] a[i]<=mn[i]+ul[i] ur[i]=a[i]-ul[i] ul[i]=min(ul[i],a[i]-ur[i])

    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t=1;
        // cin >> t;
        ll tt = 1;
        ll p=1;
        while (t--)
        {    
            solve();
            tt++;
        }
        return 0;
    }
 
/*
to get the maxsum, and minsum of a array from start but processing from end:-
suppose s is the array, sul - suffix_minsum, sur - suffix_maxsum
for (int i = n - 1; i >= 0; --i){
            int d = s[i];
            sul.push_back(min(0, sul.back() + d));
            sur.push_back(max(0, sur.back() + d));
}
*/